The emergence of dynamical complexity: An exploration using elementary cellular automata

This work concerns the interaction between two classical problems: the forecasting of the dynamical behaviors of elementary cellular automata (ECA) from its intrinsic mathematical laws and the conditions that determine the emergence of complex dynamics. To approach these problems, and inspired by the theory of reversible logical gates, we decompose the ECA laws in a “spectrum” of dyadic Boolean gates. Emergent properties due to interactions are captured generating another spectrum of logical gates. The combined analysis of both spectra shows the existence of characteristic bias in the distribution of Boolean gates for ECA belonging to different dynamical classes. These results suggest the existence of signatures capable to indicate the propensity to develop complex dynamics. Logical gates “exclusive‐or” and “equivalence” are among these signatures of complexity. An important conclusion is that within ECA space, interactions are not capable to generate signatures of complexity in the case these signatures are absent in the intrinsic law of the automaton. © 2004 Wiley Periodicals, Inc. Complexity 9: 33–42, 2004     

Algebras of Random Operators Associated to Delone Dynamical Systems

We carry out a careful study of operator algebras associated with Delone dynamical systems. A von Neumann algebra is defined using noncommutative integration theory. Features of these algebras and the operators they contain are discussed. We restrict our attention to a certain C ^*-subalgebra to discuss a Shubin trace formula.     

On the local structure of doubly laced crystals

Let g be a Lie algebra all of whose regular subalgebras of rank 2 are type A₁×A₁, A₂, or C₂, and let B be a crystal graph corresponding to a representation of g. We explicitly describe the local structure of B, confirming a conjecture of Stembridge.     

Construct non-graded bi-Frobenius algebras via quivers

Using the quiver technique we construct a class of non-graded bi-Frobenius algebras. We also classify a class of graded bi-Frobenius algebras via certain equations of structure coefficients.     

Geometric and Combinatorial Realizations of Crystal Graphs

For irreducible integrable highest weight modules of the finite and affine Lie algebras of type A and D, we define an isomorphism between the geometric realization of the crystal graphs in terms of irreducible components of Nakajima quiver varieties and the combinatorial realizations in terms of Young tableaux and Young walls. For type A_n⁽¹⁾, we extend the Young wall construction to arbitrary level, describing a combinatorial realization of the crystals in terms of new objects which we call Young pyramids. Presented by P. Littleman Mathematics Subject Classifications (2000) Primary 16G10, 17B37. Alistair Savage: This research was supported in part by the Natural Sciences and Engineering Research Council (NSERC) of Canada and was partially conducted by the author for the Clay Mathematics Institute.     

Representation of Cubic Lattices by Symmetric Implication Algebras

In this paper a cubic lattice L(S) is endowed with a symmetric implication structure and it is proved that L(S) \ {0} is a power of the three-element simple symmetric implication algebra. The Metropolis–Rota’s symmetries are obtained as partial terms in the language of symmetric implication algebras.     

Xor on one‐defect systems

We present a network experiment that investigates the computational power of cellular automata on the simplest irregular lattice. One cellular automaton whose apparent complexity increased is Rule 60, the left neighbor Xor operator. It went from being nested to complex. That makes Xor a candidate for universal computational power. We present the evidence in terms of the size of cycle lengths, transients, and size of boolean expressions. © 2006 Wiley Periodicals, Inc. Complexity 12: 13–29, 2006     

Adjugates in Banach algebras

A simple formula for the adjugate of a block triangle offers an alternative route to the determinant theory for Banach algebras.

     

Two-spin-majority cellular automaton as a model of 2D cluster and interface growth

A new probabilistic cellular automaton model is introduced to simulate cluster and interface growth in two dimensions. The dynamics of this model is an extension to higher dimensions of the compact directed percolation studied by Essam. Numerical results indicate that the two-dimensional cluster coarsening and growth can be described only approximately by the conventional cluster size scaling due to a crossover in the growth mode. The spreading of the initially flat interface follows a purely diffusional,t ^1/2, law.     

Cardy's formula for some dependent percolation models

We prove Cardy's formula for rectangular crossing probabilities in dependent site percolation models that arise from a deterministic cellular automaton with a random initial state. The cellular automaton corresponds to the zero-temperature case of Domany's stochastic Ising ferromagnet on the hexagonal lattice  (with alternating updates of two sublattices) [7]; it may also be realized on the triangular lattice 𝕋 with flips when a site disagrees with six, five and sometimes four of its six neighbors. Received: 24 December 2001